
"""
 * 230. 二叉搜索树中第K小的元素
 * 二叉搜索树：特点：
 * 1.左节点 < 根节点 < 右节点
 * 2.左子树和右子树均是二叉搜索树
 * 3.中序遍历是升序的
"""
from typing import Optional

from com.siyuan.TreeNode import TreeNode


class Solution:

    def __init__(self):
        # 序号
        self.index = 0
        # 结果
        self.res = 0

    """
    利用中序遍历，转换成求第k个元素
    """
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        self.traverse(root, k)
        return self.res

    '''遍历二叉树'''
    def traverse(self, root: Optional[TreeNode], k: int):
        if not root:
            return
        # 前序位置
        self.traverse(root.left, k)
        # 中序位置
        self.index += 1
        if k == self.index:
            self.res = root.val
            return
        self.traverse(root.right, k)
        # 后序位置